package com.way;

import com.way.printer.BinaryTreeInfo;

public class BinarySearchTree<E extends Comparable<E>> implements BinaryTreeInfo {
    private int size;
    private Node<E> root;

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        root = null;
        size = 0;
    }


    public void add(E element) {
        elementNotNullCheck(element);

        // 添加第一个元素
        if (root == null) {
            root = new Node<>(element, null);
            size++;
            return;
        }

        // 添加的不是第一个节点
        Node<E> parent = null;
        Node<E> node = root;
        int cmp = 0;
        while (node != null) {
            // 记录添加位置
            cmp = compare(element, node.element);
            // 记录父节点
            parent = node;

            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {
                node.element = element;
                return;
            }
        }

        // 添加元素
        Node<E> newNode = new Node<>(element, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;
    }

    private int compare(E e1, E e2) {
        return e1.compareTo(e2);
    }

    private void elementNotNullCheck(E element) {
        if (element == null)
            throw new IllegalArgumentException("element is null");
    }

    public void remove(E element) {
    }

    public void contains(E element) {

    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        Node<E> myNode = (Node<E>) node;
        String parentString = "null";
        if (myNode.parent != null) {
            parentString = myNode.parent.element.toString();
        }
        return myNode.element + "_p(" + parentString + ")";
    }

    private static class Node<E> {
        private E element;
        private Node<E> left;
        private Node<E> right;

        private Node<E> parent;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
    }

}
